"""
analysis of the problem trying to find a none-backtracking route from
the start point to the end point

a Node is a point on the edge
the left top point[0 , 0] the right bottom point[numCols - 1 , numRows - 1]

Node
    Members:
    x , y                   location of a node
    rightExplored           mark of whether right node is explored
    bottomExplored          mark of whether bottom node is explored
    
    Methods:
    hasRight()              does this node has right
    hasBottom()             does this node has bottom
    isRightExplored()       is the right node of this node explored
    isBottomExplored()      is the bottom node of this node explored
    setRightExplored()      set whether the right node is explored
                            only True is used here
    setBottomExplored()     set whether the bottom node is explored
                            only True is used


Steps to perform the algorithm
1 create nodes for the map
2 push the start point into a stack
3 while(stack not empty)
      top = get top from the stack

      if the top node is the end point
          pop out the end point
          continue
      
      if top has right then
          if right is not explored then
              mark top's right explored
              if right is end point then
                  numPath ++
                  continue bottom test
              else
                  
                  continue
              endif   
          endif
      endif

      bottom test

      if we got here that means no direction left for this node to explore
      pop it and set its right and bottom unexplored
"""

numRows = 21
numCols = 21

class Node:
    x = -1
    y = -1
    rightExplored = False
    bottomExplored = False
    
    def __init__(self, x , y):
        self.x = x
        self.y = y

    def isRightExplored(self):
        return self.rightExplored

    def isBottomExplored(self):
        return self.bottomExplored
        
    def setRightExplored(self):
        self.rightExplored = True

    def setBottomExplored(self):
        self.bottomExplored = True

    def hasRightNode(self):
        return self.x < numCols - 1

    def hasBottomNode(self):
        return self.y < numRows - 1


grid = []
#initialize the grid according to the numRows and numCols
for i in range(numRows):
    row = []
    for j in range(numCols):
        node = Node(j , i)
        row.append(node)
        
    grid.append(row)

stack = []
start = grid[0][0]
end = grid[numRows - 1][numCols - 1]

stack.append(start)

numPath = 0

while(len(stack) > 0):
    top = stack[len(stack) - 1]

    if(top.x == end.x and top.y == end.y):
        #pop out the end point
        top = stack.pop()
        top.rightExplored = False
        top.bottomExplored = False
        numPath += 1        
        continue
        
    
    if(top.hasRightNode()):
        if(not top.isRightExplored()):
            top.rightExplored = True
            stack.append(grid[top.y][top.x + 1])
            continue

    if(top.hasBottomNode()):
        if(not top.isBottomExplored()):
            top.bottomExplored = True
            stack.append(grid[top.y + 1][top.x])
            continue
            
    #pop here to remove the explored node        
    top = stack.pop()
    top.rightExplored = False
    top.bottomExplored = False
            
        
print("number of path " + str(numPath))    
    

    
